package leetcodehot100;


import java.util.*;

public class _114二叉树展开为链表 {
    /**
     * 给你二叉树的根结点 root ，请你将它展开为一个单链表
     * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
     * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
     */
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        firstOrder(root,list);
        for(int i=1;i<list.size();i++){
            TreeNode cur = list.get(i);
            TreeNode pre = list.get(i-1);
            pre.left = null;
            pre.right=cur;
        }
    }
    void firstOrder(TreeNode root, List<TreeNode> list){
        if (root==null)
            return;
        list.add(root);
        firstOrder(root.left,list);
        firstOrder(root.right,list);
    }

    //寻找前驱节点
    /**
     * 如果一个节点的左子节点为空，则该节点不需要进行展开操作。
     * 如果一个节点的左子节点不为空，则该节点的左子树中的最后一个节点被访问之后，该节点的右子节点被访问。
     */
    public void flatten2(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = curr.right;
                curr.left = null;
                curr.right = next;
            }
            curr = curr.right;
        }
    }
}
